package tsp;

import java.util.ArrayList;
import java.util.List;

public class Bfs {
    public static void main(String[] args) {
        int[][] nums = {{Integer.MAX_VALUE, 3, 6, 7, 5},
                {5, Integer.MAX_VALUE, 2, 3, 2},
                {6, 4, Integer.MAX_VALUE, 2, 3},
                {3, 7, 5, Integer.MAX_VALUE, 4},
                {5, 2, 3, 4, Integer.MAX_VALUE}
        };
        int len = nums.length;
        boolean[] visit = new boolean[len];
        Bfs bfs = new Bfs();
        int greedy = bfs.greedy(nums, 0, len, 0, visit, 0);
        System.out.println(greedy);
    }

    private int greedy(int[][] nums, int index, int len, int sum, boolean[] visit, int count) {
        if (count == len) {
            return sum;
        }
        int minCost = Integer.MAX_VALUE;
        int minIndex = 0;
        for (int i = 0; i < len; i++) {
            if (i == 0 && count != len - 1) {
                continue;
            }
            if (!visit[i] && nums[index][i] < minCost) {
                minCost = nums[index][i];
                minIndex = i;
            }
        }
        visit[minIndex] = true;
        return greedy(nums, minIndex, len, sum + minCost, visit, ++count);

    }
}
